package com.lun.swordtowardoffer2.c14;

import java.util.List;

public class MinimumTotal {

	
	public int minimumTotal(List<List<Integer>> triangle) {
		int size = triangle.size();
		
		int[][] dp =  new int[size][size];
		
		for(int i = 0; i < size; i++) {
			for(int j = 0; j <= i; j++) {
				dp[i][j] = triangle.get(i).get(j);
				if(i == 0 && j == 0) {
					//dp[i][j] = triangle.get(i).get(j);
				}else if(i > 0 && j == 0){
					dp[i][j] += dp[i - 1][j];
				}else if(i > 0 && j > 0 && i == j){
					dp[i][j] += dp[i - 1][j - 1];
				}else {
					dp[i][j] += Math.min(dp[i - 1][j - 1],dp[i - 1][j]);
				}
			}
		}
		
		int min = dp[size - 1][0];
		
		for(int item : dp[size - 1]) {
			min = Math.min(item, min);
		}
		
		return min;
	}
	
	//优化空间
	public int minimumTotal2(List<List<Integer>> triangle) {
		int size = triangle.size();
		int[] dp = new int[size];
		
		for(int i = 0; i < size; i++) {
			for(int j = i; j >= 0; j--) {
				int cur = triangle.get(i).get(j);
				if(i == 0 && j == 0) {
					dp[j] = cur;
					//dp[i][j] = triangle.get(i).get(j);
				}else if(i > 0 && j == 0){
					dp[j] = cur + dp[j];
				}else if(i > 0 && j > 0 && i == j){
					dp[j] = cur + dp[j - 1];
				}else {
					dp[j] = cur + Math.min(dp[j - 1],dp[j]);
				}
			}
		}
		
		int min = dp[0];
		for(int item : dp) {
			min = Math.min(item, min);
		}
		return min;
	}
}

